package com.yeung.swordoffer;

import java.util.Arrays;

/**
 * 统计一个数字在排序数组中出现的次数。
 */
public class 数字在排序数组中出现的次数 {
    public static void main(String[] args) {
        int[] ints = {1, 3, 3, 3, 3, 4, 5};
        int sou = GetNumberOfK(ints, 2);
        System.out.println(sou);
    }

    public static int GetNumberOfK(int[] array, int k) {
        if (array == null) return 0;
        Arrays.sort(array);
        int index = Arrays.binarySearch(array, k);
        if (index < 0) return 0;
        //检查这个下标是不是目标k第一次出现的位置
        while (index > 0) {
            if (array[index] != array[index - 1])
                break;
            index--;
        }
        int count = 0;
        for (int i = index; i < array.length; i++) {
            //往后计算出现了多少次
            if (array[i] == k) count++;
        }
        return count;
    }

    public static int binarySearch(int[] arr, int low, int high, int k) {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (k < arr[mid])
            return binarySearch(arr, low, mid - 1, k);
        else if (k > arr[mid])
            return binarySearch(arr, mid + 1, high, k);
        else return mid;

    }

}
